import java.util.*;

/**
 * 49. Group Anagrams 字母异位词分组
 * https://leetcode-cn.com/problems/group-anagrams/
 */
class GroupAnagrams {
    /**
     * 方法：使用哈希表将字母异位词分组
     * 通过将每个字符串排序后作为哈希表的键，将具有相同字母组成的字符串分组在一起
     * 
     * Args:
     *     strs: String[] - 输入的字符串数组
     * 
     * Returns:
     *     List<List<String>> - 分组后的字母异位词列表，每个子列表包含一组字母异位词
     * 
     * Time: O(n * klogk) - 其中n是字符串数量，k是字符串最大长度，需要对每个字符串进行排序
     * Space: O(n * k) - 需要存储所有字符串及其排序后的结果
     */
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> m = new HashMap<>();
        for(String s : strs){
            char[] sortedS = s.toCharArray();
            Arrays.sort(sortedS);
            m.computeIfAbsent(new String(sortedS), k -> new ArrayList<>()).add(s);
        }
        return new ArrayList<>(m.values());
    }

    /**
     * 方法：使用字符计数作为哈希表的键
     * 通过统计每个字符串中各个字符的出现次数，构建唯一的键来分组字母异位词
     * 
     * Args:
     *     strs: String[] - 输入的字符串数组
     * 
     * Returns:
     *     List<List<String>> - 分组后的字母异位词列表，每个子列表包含一组字母异位词
     * 
     * Time: O(n * k) - 其中n是字符串数量，k是字符串最大长度，需要遍历每个字符串统计字符
     * Space: O(n * k) - 需要存储所有字符串及其字符计数结果
     */
    public List<List<String>> groupAnagrams1(String[] strs) {
        Map<String, List<String>> m = new HashMap<>();
        for(String s : strs){
            // 使用字符计数作为键
            int[] count = new int[26];
            for(char c : s.toCharArray()){
                count[c - 'a']++;
            }
            // 构建键字符串，如#1#2#0...#3
            StringBuilder sb = new StringBuilder();
            for(int i = 0; i< 26; i++){
                sb.append("#");
                sb.append(count[i]);
            }
            String key = sb.toString();
            m.computeIfAbsent(key, k -> new ArrayList<>()).add(s);

        }
        return new ArrayList<>(m.values());
    }
}